from typing import List
from functools import  cache

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        max_len=max(map(len,wordDict))  # 用于限制下面j的循环次数
        words=set(wordDict) # 便于快速判断 s[j:i] in words

        # 定义状态为 dfs(i)，表示能否把前缀 s[:i]（表示 s[0] 到 s[i−1] 这段子串）划分成若干段，使得每段都在 wordDict 中。
        @cache
        def dfs(i):
            if i==0:
                return True
            for j in range(i-1,max(i-max_len-1,-1),-1):
                #
                if s[j:i] in words and dfs(j):
                    return True
            return False
        return dfs(len(s))